package com.jeff.test;

public class IslandCounter {
    /**
     * 计算网格中岛屿的数量。
     * 岛屿是由 '1' 组成的并且相邻的 '1' 形成的连通区域。
     * 网格是由字符数组表示的，其中 '1' 表示陆地，'0' 表示水。
     *
     * @param grid 表示网格的二维字符数组。
     * @return 返回网格中岛屿的数量。
     */
    public int numIslands(char[][] grid) {
        // 检查网格是否为空或不存在任何岛屿
        if (grid == null || grid.length == 0) {
            return 0;
        }

        // 初始化岛屿数量计数器
        int count = 0;
        // 遍历网格中的每个元素
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                // 当发现陆地时
                if (grid[i][j] == '1') {
                    // 使用深度优先搜索标记并访问所有连接的陆地
                    dfs(grid, i, j);
                    // 岛屿数量加一
                    count++;
                }
            }
        }
        // 返回岛屿的总数
        return count;
    }


    /**
     * 深度优先搜索（DFS）函数，用于寻找海岛上所有的陆地。
     * 通过遍历网格中的每个位置，如果该位置是陆地（值为'1'），则将其标记为已访问（值为'0'），
     * 并继续搜索其相邻的位置，以找到所有的连通陆地。
     *
     * @param grid 二维字符数组，表示网格地图，其中'1'表示陆地，'0'表示水域。
     * @param i 当前位置的行索引。
     * @param j 当前位置的列索引。
     */
    private void dfs(char[][] grid, int i, int j) {
        // 检查当前位置是否越界或不是陆地，如果是，则返回。
        if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] != '1') {
            return;
        }

        // 将当前位置标记为已访问，避免重复访问。
        // 将访问过的陆地标记为已访问
        grid[i][j] = '0';

        // 向上、下、左、右四个方向递归调用DFS，搜索相邻的陆地。
        // 探索上下左右四个方向
        dfs(grid, i + 1, j);
        dfs(grid, i - 1, j);
        dfs(grid, i, j + 1);
        dfs(grid, i, j - 1);
    }


    public static void main(String[] args) {
        char[][] grid  = {
                {'0', '0', '0', '0', '0'},
                {'0', '0', '0', '0', '0'},
                {'0', '0', '0', '0', '0'},
                {'0', '0', '0', '0', '0'}
        };


        IslandCounter islandCounter = new IslandCounter();
        int count = islandCounter.numIslands(grid);
        System.out.println(count);
    }
}

